﻿using System;
using System.Collections;

namespace namespace_0426
{
  class class_0426
  {
    public void mains()
    {
      class_0426 c_0426 = new class_0426();
      string[] strs = { "flower", "flow", "flight" };
      string[] strs2 = { "dog", "racecar", "car" };
      string LongestCommonPrefix = c_0426.LongestCommonPrefix(strs2);
      Console.WriteLine("LongestCommonPrefix:" + LongestCommonPrefix);

      // int a = 12321;
      // Boolean IsPalindrome = c_0426.IsPalindrome(a);
      // Console.WriteLine("IsPalindrome:" + IsPalindrome);

      // string s = "{[]}";
      // string s2 = "()}";
      // Boolean IsValid = c_0426.IsValid(s2);
      // Console.WriteLine("IsValid:" + IsValid);

      // string haystack = "hello";
      // string needle = "lol";
      // int StrStr = c_0426.StrStr(haystack, needle);
      // Console.WriteLine("StrStr:" + StrStr);

      int[] nums = { 2, 4, 5, 6, 7 };
      int num = 5;
      int SearchInsert = c_0426.SearchInsert(nums, num);
      Console.WriteLine("SearchInsert:" + SearchInsert);
    }

    // 最长公共前缀
    public string LongestCommonPrefix(string[] strs)
    {
      string br = "";
      if (strs.Length > 0)
      {
        string str = strs[0];
        string brr = "";
        for (int i = 0; i < str.Length; i++)
        {
          string s = "";
          string sL = "";
          for (int j = 0; j < strs.Length; j++)
          {
            if (strs[j].Length > i && str[i] == strs[j][i])
            {
              s = str[i].ToString();
              sL += str[i];
            }
          }
          if (sL.Length == strs.Length && brr.Length == i)
          {
            brr += s;
          }
        }
        br = brr;
      }
      return br;
    }

    // 回文数
    public bool IsPalindrome(int x)
    {
      Boolean br = true;
      string str = x.ToString();
      int L = (int)Math.Floor((double)str.Length / 2);
      for (int i = 0; i < L; i++)
      {
        if (str[i] != str[str.Length - 1 - i])
        {
          br = false;
        }
      }
      return br;
    }

    // 有效的括号
    // 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效
    public bool IsValid(string s)
    {
      Boolean br = true;
      if ((s != "" && s.Length < 2) || s.Length % 2 == 1)
      {
        br = false;
      }
      else
      {
        int left = 0;
        int right = 0;
        // 堆栈（Stack）
        Stack st = new Stack();
        for (int i = 0; i < s.Length; i++)
        {
          if (s[i] == '(' || s[i] == '[' || s[i] == '{')
          {
            //添加元素
            st.Push(s[i]);
            left++;
          }
          if ((s[i] == ')' || s[i] == ']' || s[i] == '}') && st.Count > 0)
          {
            string ss = st.Pop().ToString();
            string ssBack = "";
            switch (ss)
            {
              case "(":
                ssBack = ")";
                break;
              case "[":
                ssBack = "]";
                break;
              case "{":
                ssBack = "}";
                break;
            }
            if (ssBack != s[i].ToString())
            {
              br = false;
            }
            right++;
          }
        }
        if (left != right)
        {
          br = false;
        }
      }
      return br;
    }

    // 实现 strStr()
    public int StrStr(string haystack, string needle)
    {
      int br = -1;
      if (haystack.Length > 0 && needle.Length > 0)
      {

      }
      else if (haystack.Length == 0 && needle.Length == 0)
      {
        br = 0;
      }
      else
      {
        int i = haystack.IndexOf(needle);
        if (i >= 0)
        {
          br = i;
        }
      }
      return br;
    }

    // 搜索插入位置
    public int SearchInsert(int[] nums, int target)
    {
      int br = 0;
      if (nums.Length > 0)
      {
        for (int i = 0; i < nums.Length; i++)
        {
          if (nums[i] >= target)
          {
            br = i;
            break;
          }
        }
        if (nums[nums.Length - 1] < target)
        {
          br = nums.Length;
        }
      }
      return br;
    }

  }
}
